#include <iostream>


using namespace std;

struct Node{
    int data;
    Node *next;
    Node *prev;
    Node():data(0),next(NULL),prev(NULL){}
    Node(int x):data(x),next(NULL),prev(NULL){}
    Node(int x,Node *n,Node *p):data(x),next(n),prev(p){}
};


class DoubleCycleLinkList{
public:
    DoubleCycleLinkList()
        :head_(NULL)
    {
        Node *p = new Node();
        head_ = p;
        head_->next = head_;
        head_->prev = head_;
    }
    ~DoubleCycleLinkList(){
        Node *p = head_;
        while(p){
            Node *q = p;
            p = p->next;
            delete q;
        }
        head_ = NULL;
    }
    void HeadInsert(int x);
    void TailInsert(int x);
    void showlinklist();
    bool find(int x);
    void remove(int x);
private:
    Node *head_;
};

void DoubleCycleLinkList::HeadInsert(int x){
    Node *p = new Node(x);
    p->next = head_->next;
    head_->next = p;
    p->prev = head_;
    p->next->prev = p;
}

void DoubleCycleLinkList::TailInsert(int x){
    Node *p = new Node(x);
    p->prev = head_->prev;
    p->next = head_;
    head_->prev->next = p;
    head_->prev = p;
}

void DoubleCycleLinkList::showlinklist(){
    Node *p = head_->next;
    while(p != head_){
        cout << p->data << " ";
        p = p->next;
    }
    cout<<endl;
}

bool DoubleCycleLinkList::find(int x){
    Node *p = head_->next;
    while(p != head_){
        if(p->data == x){
            cout << "find " << x << endl;
            cout << "p is " << p << endl;
            cout << "p->next is " << p->next << "p->next->data is " << p->next->data << endl;
            cout << "p->prev is " << p->prev << "p->prev->data is " << p->prev->data << endl;
            return true;
        }
        p = p->next;
    }
    return false;
}

void DoubleCycleLinkList::remove(int x){
    if(head_ == nullptr) return;
    Node *p = head_->next;
    while(p != head_){
        if(p->data == x){
            p->prev->next = p->next;
            p->next->prev = p->prev;
            cout << "remove " << x << endl;
            cout << "p is " << p << endl;
            Node *q = p;
            p = p->next;
            delete q;
            continue;
        }
        p = p->next;
        cout << "p is " << p << endl;
        cout << "p->data is " << p->data << endl;
    }
}

int main ()
{
    DoubleCycleLinkList list;
    list.HeadInsert(1);
    list.HeadInsert(2);
    list.TailInsert(3);
    list.TailInsert(4);
    list.HeadInsert(5);
    list.TailInsert(6);
    list.TailInsert(3);
    list.TailInsert(4);
    list.TailInsert(3);
    list.TailInsert(9);
    list.showlinklist();

    list.find(3);

    list.remove(3);
    list.showlinklist();

    list.find(3);

    return 0;
}